from collections import defaultdict
from typing import List


class DSU:
    def __init__(self, n: int):
        self._n = n
        self._array = [i for i in range(n)]
        self._size = [1] * n
        self._group_num = n

    def find(self, i: int) -> int:
        """查询i所在的连通分支:O(1)"""
        if self._array[i] != i:
            self._array[i] = self.find(self._array[i])
        return self._array[i]

    def union(self, i: int, j: int) -> bool:
        """合并i和j所属的连通分支:O(1)"""
        i, j = self.find(i), self.find(j)
        if i != j:
            self._group_num -= 1
            if self._size[i] >= self._size[j]:
                self._array[j] = i
                self._size[i] += self._size[j]
            else:
                self._array[i] = j
                self._size[j] += self._size[i]
            return True
        else:
            return False

    def is_connected(self, i: int, j: int) -> bool:
        return self.find(i) == self.find(j)

    def refresh(self):
        """令所有连通分支在array中的值相同:O(N)"""
        for i in range(self._n):
            self.find(i)

    @property
    def array(self) -> list:
        return self._array

    @property
    def group_num(self) -> int:
        """计算连通分支数量:O(1)"""
        return self._group_num

    @property
    def max_group_size(self) -> int:
        """计算最大连通分支包含的数量:O(N)"""
        import collections
        return max(collections.Counter(self._array).values())


class PrimeFactorDecompositioner:
    """质因数分解计算器"""

    def __init__(self, size):
        """size=支持分解的最大数"""
        self.size = size
        self.primes = self.get_primes(int(pow(self.size, 0.5)) + 1)  # 计算需要的质因数列表

    def get_prime_factors(self, x):
        """计算x的质因数列表（如果同一个质因数有多个，则返回多个）"""
        res = []
        for prime in self.primes:
            if prime > x:
                break
            while x % prime == 0:
                res.append(prime)
                x //= prime
        if x > 1:
            res.append(x)
        return res

    @staticmethod
    def get_primes(n: int) -> list:
        if n < 2:
            return []

        num_list = [True] * n
        num_list[0], num_list[1] = False, False

        for i in range(2, int(pow(n, 0.5)) + 1):
            if num_list[i]:  # 如果i为质数(不是任何质数的倍数)
                num_list[i * i::i] = [False] * ((n - i * i - 1) // i + 1)  # 因为要包含i*i所以需要+1；因为n不在列表里，所以需要-1

        return [i for i in range(n) if num_list[i]]


class Solution:
    # 只要两个因子同时出现在一个数，则两个因子的数都可以随便调换，例如[3,7,21]
    def gcdSort(self, nums: List[int]) -> bool:
        size = len(nums)

        # 初始化质因数分解计算器
        pf = PrimeFactorDecompositioner(10 ** 5 + 1)

        # 定义并查集
        dsu = DSU(size)

        # 定义每个因子的合并位置
        factor_idx = {}

        # 计算每一个数可以交换的组
        for i in range(size):
            num = nums[i]
            for factor in set(pf.get_prime_factors(num)):
                if factor not in factor_idx:
                    factor_idx[factor] = i
                else:
                    dsu.union(i, factor_idx[factor])
        dsu.refresh()

        # 升序排序每一组可交换的数
        stat = dsu.array
        group = defaultdict(list)
        for i in range(size):
            group[stat[i]].append(nums[i])

        for lst in group.values():
            lst.sort(reverse=True)

        last = 0
        for i in range(size):
            now = group[stat[i]].pop()
            if now < last:
                return False
            last = now

        return True


if __name__ == "__main__":
    print(Solution().gcdSort(nums=[7, 21, 3]))  # True
    print(Solution().gcdSort(nums=[5, 2, 6, 2]))  # False
    print(Solution().gcdSort(nums=[10, 5, 9, 3, 15]))  # True
